package TP6;

/**
 * Created by IntelliJ IDEA.
 * User: pc
 * Date: 18/11/11
 * Time: 20:40
 * To change this template use File | Settings | File Templates.
 */
public abstract class InterpolatedSearchArray<K, V> extends AbstractSearchArray<K, V> {

    public int search(Object o, int i, int j){
        int k = o.hashCode();
        if((j-i)>10){
            int ki = (entryList.get(i).getKey()).hashCode();
            int kj = (entryList.get(j).getKey()).hashCode();
            double d = ((double)(k - ki)/(double)(kj - ki))*(j - i - 1);
            int id = (int) d;
            if(k<ki){
                return search(o, i, id-1);
            }else if(k>ki){
                return search(o, id+1, j);
            }else{
                return id;
            }
        }else{
            for(int a=i; a<j; a++){
                if(k == entryList.get(a).getKey().hashCode()){
                    return a;
                }
            }
        }
        return -1;
    }

}
